Printers typically provide a limited number of output possibilities, and are commonly binary, i.e., they produce either a spot or no spot at a given location (although multilevel printers beyond binary are known). Thus, given an image or a separation in a color image having perhaps 256 possible density levels, a set of binary printer signals must be produced representing the contone effect. In such arrangements, over a given area in the separation having a number of contone pixels therein, each pixel value in an array of contone pixels within the area is compared to one of a set of preselected thresholds as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is a contone (continuous tone image), some of the thresholds will be exceeded, i.e. the image value at that specific location is larger than the value of the threshold for that same location, while others are not. In the binary case, the pixels or cell elements for which the thresholds are exceeded might be printed as black or some color, while the remaining elements are allowed to remain white or uncolored, dependent on the actual physical quantity described by the data. The described halftoning or dithering method produces an output pattern that is periodic or quasi-periodic in the spatial coordinates.
Dithering creates problems in color document reproduction where the repeating pattern of a screen through the image, when superposed over similar repeating patterns in multiple separations, can cause moire or other artifacts, particularly in printing systems with less than ideal registration between separations.
The binary halftone output is the result of the point-to-point comparison. For a dithering screen with a fixed number of elements, N, there are N possible different threshold values, therefore, the halftone image can simulate N+1 different gray levels. In the following discussion we use 1 to N to represent the N threshold values and use the following dithering rule:
If the input is less than the threshold, the output is zero, or black; otherwise, the output is one, or white. PA1 a memory, storing a set of halftone threshold level signals, each threshold signal corresponding to a unique location in a halftone cell; PA1 a comparator, receiving said image signal and one of the halftone threshold signals from the memory, and producing an output signal at one of c possible levels, varying according to the comparison of said halftone threshold signal to said image signal to cause marking at a selected location on a substrate; PA1 said set of threshold level signals together forming a screen matrix arranged for use with respect to the image to generate multiple clusters of printed spots within a single repetition of the screen and generated by a dot clustering optimization process which optimizes the screen by approximating a condition where: PA1 1. At any level of the input, all clusters have the same shape and the same size; and PA1 2. All adjacent clusters are equal-distance separated.
The screened output forms a repeating cluster of spots, or a dot. Since the cluster size defines the line frequency of created halftone images, screens with a single cluster usually are limited in their size and do not provide enough simulated gray levels. One solution is using larger screens with multiple clusters. There are many dual dots and quad dots well designed and widely used. However, the design of halftone screens with a large number of clusters is very difficult by current techniques, which require frequent visual examination of trials and the experience of experts.
One of the advantages of stochastic, or non-periodic screening over periodic screening is the suppression of moire. In this respect, note also, U.S. Pat. No. 5,394,252 to Holladay et al.
In U.S. Pat. No. 5,341,228 to Parker et al., a halftoning system using a stochastic process known as a blue noise mask is described. Briefly, the procedure can be described as follows: 1) Starting at one gray level with a chosen dot pattern, or "seed", the process iteratively uses a Fast Fourier Transform (FFT) techniques with a "blue noise" filter to redistribute all spots in dot pattern and eliminate large visual "clumps"; 2) Next, the dot pattern is processed at the next gray level by increasing (or decreasing) certain number of black spots on the previously determined dot pattern. Existing black (or white) spots are not moved. The same filtering technique is used to distribute newly added (or subtracted) dots; 3) Step 2 is then repeated for all gray levels sequentially. At each step, the width of the blue-noise filter varies by an amount corresponding to the current gray level; 4). The summation of dot patterns for each gray levels is the blue noise mask generated. The mask is then used to generate a halftone screen. The result of described sequential design procedure strongly depends on the choice of the seed pattern. If the output is not a satisfactory one, the design procedure has to start over again by choosing different seed or changing the blue noise filter. Since the threshold value of each pixel of the dithering screen is fixed at the gray level when the corresponding dot is added (or eliminated), the freedom to locate undetermined pixels is getting smaller and smaller while the design sequence is approaching the end. These constraints limit further improvement of the image quality generated by blue noise masks.
U.S. Pat. No. 4,485,397 to Scheuter et al. describes a method for generating a non-periodic halftone distribution by determining areas of constant or nearly constant input density and by distributing a precalculated number of print dots inside each area based on a random or pseudo random number and some spatial constraints.
U.S. Pat. No. 4,876,611 to Fischer et al. describes another stochastic screening algorithm in which the print/no-print decision is based on a recursive subdivision of the print field maintaining average density over the larger print field.
A non-periodic halftoning scheme based on a pulse-density modulation is taught in "Binarization using a two-dimensional pulse-density modulation", by R. Eschbach and R. Hauck, Journal of the Optical Society of America A, 4, 1873-1878 (1987); and "Pulse-density modulation on rastered media: combining pulse-density modulation and error diffusion", by R. Eschbach, Journal of the Optical Society of America A, 7, 708-716 (1990). In pulse-density modulation a mathematical model is used that guarantees the local density of print pulses as a function of the input image data.
In U.S. patent application Ser. No. 08/663,419 by Shen-ge Wang, an idealized stochastic screen is characterized by having all of the predominant color dots (black or white) uniformly distributed. A process is described to approach this optimization by iteratively selecting pairs of threshold levels in the screen matrix, and measuring the approach to the idealized stochastic screen. The threshold values are then swapped in position to determine whether the swap improves the measurement or not. If it does, the swap is maintained. The process is iterated until the desired result is obtained.
The above references are herein incorporated by reference for their teachings.